#include<iostream>
#include<time.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<string>
using namespace std;

/*

	学生仅需针对填入FIFO和LRU,optim函数进行编程即可，具体会使用函数如下：
	函数及其参数说明：
		create_data：创建一个大小为N的数据
			data:用于存储数据的数组
			N:表示数据的大小
		FIFO：实现先进先出算法的函数，返回值为float类型
			data:使用的数据
			N:数据的大小
			memory_size:虚拟存储区大小
		LRU：实现最近最少使用算法的函数，返回值为float类型
			data:使用的数据
			N:数据的大小
			memory_size:虚拟存储区大小
		optim：实现最优化的函数，能够保证最大的调度
			data:使用的数据
			N:数据的大小
			memory_size:虚拟存储区大小
*/

void create_data(int data[], int N, int seed = 333) {
	srand(seed);
	for (int i = 0; i < N; i++) {
		data[i] = rand() % 5;
	}
}
void reset_data(int data[], int N) {
	for (int i = 0; i < N; i++) {
		data[i] = -1;
	}
}
void output_data(int data[], int N) {
	for (int i = 0; i < N; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
}

void show_output(int arr[], const int size) {
	for (int i = 0; i < size; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

float FIFO(int arr[], const int& N, const int& memory_Size, int output[]) {
	//todo finish the func;
	queue<int> q;
	float hitrate = 0;
	for (int i = 0; i < N; i++) {
		int sz = q.size();
		bool hit = false;
		while (sz-- > 0) {
			int j = q.front(); q.pop();
			if (j == arr[i]) {
				hit = true;
				hitrate += 1;
			}
			q.push(j);
		}
		if (!hit) {
			if (q.size() == memory_Size) {
				output[i] = q.front();
				q.pop();
			}
			q.push(arr[i]);
		}
	}
	return hitrate / N;
}

float LRU(int arr[], const int& N, const int& memory_Size, int output[]) {
	//todo finish the func;
	vector<vector<int>> cache(N, vector<int>(2, -1));
	float hit_rate = 0.0;
	for (int i = 0; i < N; i++) {
		int last = 0;
		int last_id = -1;
		bool hit = false;
		for (int j = 0; j < memory_Size; ++j) {
			if (cache[j][0] == arr[i]) {
				hit_rate += 1.0;
				cache[j][1] = i;
				hit = true;
				break;
			}
			else if (cache[j][1] == -1) {
				cache[j][0] = arr[i];
				cache[j][1] = i;
				hit = true;
				break;
			}
			else {
				if (i - cache[j][1] > last) {
					last = i - cache[j][1];
					last_id = j;
				}
			}
		}
		if (!hit) {
			output[i] = cache[last_id][0];
			cache[last_id][0] = arr[i];
			cache[last_id][1] = i;
		}
	}
	return hit_rate / N;
}

int help_optim(vector<int>& input, vector<int>& memory, int t, const int& N, const int& memory_size, vector<unordered_map<string, int>>& k);
float optim(int arr[], const int& N, const int& memory_Size, int output[]) {
	vector<int> arrs(N, 0);
	for (int i = 0; i < N; i++)arrs[i] = arr[i];
	vector<int> cache(memory_Size, -1);
	vector<unordered_map<string, int>> m(N);
	return (float)help_optim(arrs, cache, 0, N, memory_Size, m) / N;
}

int help_optim(vector<int>& input, vector<int>& memory, int t, const int& N, const int& memory_size, vector<unordered_map<string, int>>& k) {
	sort(memory.begin(), memory.end());
	string key = "";
	for (int i : memory) {
		key += to_string(i) + "_";
	}
	if (t == input.size())return 0;

	if (k[t].count(key))return k[t][key];
	int id = -1;
	for (int i = 0; i < memory_size; i++) {
		if (memory[i] == -1)id = i;
		if (memory[i] == input[t]) {
			return k[t][key] = 1 + help_optim(input, memory, t + 1, N, memory_size, k);
		}
	}
	if (id == -1) {
		int ans = 0;
		for (int i = 0; i < memory_size; ++i) {
			int temp = memory[i];
			memory[i] = input[t];
			ans = max(ans, help_optim(input, memory, t + 1, N, memory_size, k));
			memory[i] = temp;
		}
		return k[t][key] = ans;
	}
	memory[id] = input[t];
	return k[t][key] = help_optim(input, memory, t + 1, N, memory_size, k);
}



int main() {
	const int data_num = 30;
	const int seed = 333;
	int max_memory_size = 5;
	int data[data_num];
	int output[data_num];
	create_data(data, data_num, seed);
	cout << "The data input is: " << endl;
	for (int i = 0; i < data_num; ++i)cout << data[i] << " ";
	cout << endl;
	for (int j = 2; j < max_memory_size; j++) {
		cout << "when cache size is " << j << endl;
		reset_data(output, data_num);
		cout << "The hit rate of FIFO is: " << FIFO(data, data_num, j, output) << endl;
		cout << "The output in FIFO is: " << endl;
		show_output(output, data_num);
		reset_data(output, data_num);
		cout << "The hit rate of LRU is: " << LRU(data, data_num, j, output) << endl;
		cout << "The output in LRU is: " << endl;
		show_output(output, data_num);
		reset_data(output, data_num);
		//cout << "The hit rate of Optim is: " << optim(data, data_num, j, output) << endl;
		cout << "\n";
	}
}